package newcoder_exp.justPractise;
import java.util.Arrays;

import org.junit.*;
public class Pra12_sets {
    
    //集合划分
    /* 
        计算n个元素有多少个各不相同的**非空**子集合
    */
    public long countSets(int n) {
        long sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += count(n, i);
        }
        //若带上空集，需要将sum++
        return sum;
    }

    public long count(int n, int m) {
        if (n < m || m == 0) 
            return 0;
        if (n == 0 || m == n)
            return 1;
        return m * count(n - 1, m) + count(n - 1, m - 1);
    }

    public long countSets2(int n) {
        //f[i][j] i个元素的子集个数
        long[][] f = new long[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            f[i][i] = 1;
            f[0][i] = 1;
        }
        long sum = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                f[i][j] = j * f[i - 1][j] + f[i - 1][j - 1];
                if (i == n) {
                    sum += f[i][j];
                }
            }
        }
        sum++;
        return sum;
    }

    @Test
    public void test() {
        System.out.println(countSets(24));
        System.out.println(countSets2(24));        

    }
}
